home *** CD-ROM | disk | FTP | other *** search
/ Info-Mac 11 / Info-Mac_XI_Disc_1.cdr_ / Info-Mac XI Disc 1.cdr / Programs / Science & Math / MacEspresso 1.0 / espresso / dominate.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-02-26  |  2.2 KB  |  90 lines  |  [TEXT/R*ch]
  1. #include "mincov_int.h"
  2.  
  3.  
  4. int 
  5. sm_row_dominance(A)
  6. sm_matrix *A; 
  7. {
  8.     register sm_row *prow, *prow1;
  9.     register sm_col *pcol, *least_col;
  10.     register sm_element *p, *pnext;
  11.     int rowcnt;
  12.  
  13.     rowcnt = A->nrows;
  14.  
  15.     /* Check each row against all other rows */
  16.     for(prow = A->first_row; prow != 0; prow = prow->next_row) {
  17.  
  18.     /* Among all columns with a 1 in this row, choose smallest */
  19.     least_col = sm_get_col(A, prow->first_col->col_num);
  20.     for(p = prow->first_col->next_col; p != 0; p = p->next_col) {
  21.         pcol = sm_get_col(A, p->col_num);
  22.         if (pcol->length < least_col->length) {
  23.         least_col = pcol;
  24.         }
  25.     }
  26.  
  27.     /* Only check for containment against rows in this column */
  28.     for(p = least_col->first_row; p != 0; p = pnext) {
  29.         pnext = p->next_row;
  30.  
  31.         prow1 = sm_get_row(A, p->row_num);
  32.         if ((prow1->length > prow->length) ||
  33.                   (prow1->length == prow->length && 
  34.                   prow1->row_num > prow->row_num)) {
  35.         if (sm_row_contains(prow, prow1)) {
  36.             sm_delrow(A, prow1->row_num);
  37.         }
  38.         }
  39.     }
  40.     }
  41.  
  42.     return rowcnt - A->nrows;
  43. }
  44.  
  45. int 
  46. sm_col_dominance(A, weight)
  47. sm_matrix *A;
  48. int *weight;
  49. {
  50.     register sm_row *prow;
  51.     register sm_col *pcol, *pcol1;
  52.     register sm_element *p;
  53.     sm_row *least_row;
  54.     sm_col *next_col;
  55.     int colcnt;
  56.  
  57.     colcnt = A->ncols;
  58.  
  59.     /* Check each column against all other columns */
  60.     for(pcol = A->first_col; pcol != 0; pcol = next_col) {
  61.     next_col = pcol->next_col;
  62.  
  63.     /* Check all rows to find the one with fewest elements */
  64.     least_row = sm_get_row(A, pcol->first_row->row_num);
  65.     for(p = pcol->first_row->next_row; p != 0; p = p->next_row) {
  66.         prow = sm_get_row(A, p->row_num);
  67.         if (prow->length < least_row->length) {
  68.         least_row = prow;
  69.         }
  70.     }
  71.  
  72.     /* Only check for containment against columns in this row */
  73.     for(p = least_row->first_col; p != 0; p = p->next_col) {
  74.         pcol1 = sm_get_col(A, p->col_num);
  75.         if (weight != 0 && weight[pcol1->col_num] > weight[pcol->col_num])
  76.         continue;
  77.         if ((pcol1->length > pcol->length) ||
  78.            (pcol1->length == pcol->length && 
  79.                    pcol1->col_num > pcol->col_num)) {
  80.         if (sm_col_contains(pcol, pcol1)) {
  81.             sm_delcol(A, pcol->col_num);
  82.             break;
  83.         }
  84.         }
  85.     }
  86.     }
  87.  
  88.     return colcnt - A->ncols;
  89. }
  90.